#pragma once
#include <iostream>
#include <assert.h>
#include <stdbool.h>
using namespace std;
enum color {
	RED,
	BLACK
};
template <class k, class v>
struct RBNode {
	RBNode<k, v>* _left;
	RBNode<k, v>* _right;
	RBNode<k, v>* _parent;
	pair<k, v> _kv;
	color _col;
	RBNode(const pair<k, v>& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(RED)
	{}
};
template <class k, class v>
class RBtree {
	typedef RBNode<k, v> Node;
public:
	RBtree()
		:_root(nullptr)
	{}
	void RotateL(Node* parent) {
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		Node* PPNode = parent->_parent;
		parent->_right = subrl;
		if (subrl)
		{
			subrl->_parent = parent;
		}
		subr->_left = parent;
		parent->_parent = subr;
		if (parent == _root)
		{
			_root = subr;
			_root->_parent = nullptr;
		}
		else
		{
			if (PPNode->_left == parent)
			{
				PPNode->_left = subr;
			}
			else if (PPNode->_right == parent)
			{
				PPNode->_right = subr;
			}
			subr->_parent = PPNode;
		}
	}
	void RotateR(Node* parent) {
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		Node* PPNode = parent->_parent;
		parent->_left = sublr;
		if (sublr)
		{
			sublr->_parent = parent;
		}
		subl->_right = parent;
		parent->_parent = subl;
		if (parent == _root)
		{
			_root = subl;
			subl->_parent = nullptr;
		}
		else
		{
			if (PPNode->_left == parent)
			{
				PPNode->_left = subl;
			}
			else if (PPNode->_right == parent)
			{
				PPNode->_right = subl;
			}
			subl->_parent = PPNode;
		}
	}
	bool Insert(const pair<k, v>& val) {
		if (Find(val.first) != nullptr)
			return false;
		if (_root == nullptr)
		{
			_root = new Node(val);
			_root->_col = BLACK;
		}
		else {
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (val.first < cur->_kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (val.first > cur->_kv.first) {
					parent = cur;
					cur = cur->_right;
				}
				else return false;
			}
			cur = new Node(val);
			if (val.first < parent->_kv.first)
			{
				parent->_left = cur;
			}
			if (val.first > parent->_kv.first)
			{
				parent->_right = cur;
			}
			cur->_parent = parent;
			while (parent && parent->_col == RED) {
				Node* grandfather = parent->_parent;
				Node* uncle = nullptr;
				if (parent == grandfather->_left)
				{
					uncle = grandfather->_right;
					if (uncle && uncle->_col == RED)
					{
						uncle->_col = parent->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else {
						if (cur == parent->_left)
						{
							RotateR(parent);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else {
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
				}
				if (parent == grandfather->_right)
				{
					uncle = grandfather->_left;
					if (uncle && uncle->_col == RED)
					{
						uncle->_col = parent->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else {
						if (cur == parent->_right)
						{
							RotateL(parent);
							parent->_col = BLACK;
							grandfather->_col = RED;
						}
						else {
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = BLACK;
							grandfather->_col = RED;
						}
						break;
					}
				}
			}
		}
		return true;
	}
	Node* Find(const k& k) {
		Node* cur = _root;
		while (cur) {
			if (k < cur->_kv.first)
				cur = cur->_left;
			else if (k > cur->_kv.first)
				cur = cur->_right;
			else
				return cur;
		}
		return nullptr;
	}
	Node* LeftMost() {
		Node* cur = _root;
		while (cur->_left) {
			cur = cur->_left;
		}
		return cur;
	}
	Node* RightMost() {
		Node* cur = _root;
		while (cur->_right) {
			cur = cur->_right;
		}
		return cur;
	}
	Node*& GetRoot() {
		return _root;
	}
	bool IsValidRBTRee() {
		if (_root->_col == RED)
			return false;
		Node* cur = _root;
		int num = 0;
		while (cur) {
			if (cur->_col == BLACK)
				num++;
			cur = cur->_left;
		}
		return _IsValidRBTRee(_root, 0, num);
	}
	void InOrder() {
		return _InOrder(_root);
	}
private:
	void _InOrder(Node* root) {
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << endl;
		_InOrder(root->_right);
	}
	bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {
		if (pRoot == nullptr)
		{
			if (blackCount != pathBlack)
				return false;
			else
				return true;
		}
		if (pRoot->_col == RED && pRoot->_parent->_col == RED)
		{
			return false;
		}
		if (pRoot->_col == BLACK)
		{
			blackCount++;
		}
		return _IsValidRBTRee(pRoot->_left, blackCount, pathBlack) && _IsValidRBTRee(pRoot->_right, blackCount, pathBlack);
	}
	Node* _root;
};
